/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 *
 * https://leetcode-cn.com/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (64.58%)
 * Likes:    1049
 * Dislikes: 0
 * Total Accepted:    310.2K
 * Total Submissions: 480.1K
 * Testcase Example:  '[1,1,2]'
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * ⁠[1,2,1],
 * ⁠[2,1,1]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     vector<int> path;
//     vector<vector<int>> res;
//     void backtracking(vector<int>& nums, vector<bool>& used) {
//         if(path.size() == nums.size()) {
//             res.push_back(path);
//             return;
//         }

//         for(int i = 0; i < nums.size(); i++) {
//             // 树层--横向 
//             // 树枝--纵向

//             // false树层(横向)去重首选，因为可以提高效率
//             // 树层去重，保留树枝(纵深)重复的
//             if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;

//             // true 树枝(纵深)去重次选，没树层(横向)去重效率高
//             // 树枝去重，保留树层重复的，
//             // if(i > 0 && nums[i] == nums[i-1] && used[i-1] == true) continue;

//             if(used[i] == false) {
//                 path.push_back(nums[i]);
//                 used[i] = true;
//                 backtracking(nums, used);
//                 used[i] = false;
//                 path.pop_back();
//             }
//         }

//     }
// public:
//     vector<vector<int>> permuteUnique(vector<int>& nums) {
//         path.clear();
//         res.clear();
//         sort(nums.begin(), nums.end());
//         vector<bool> used(nums.size(), false);
//         backtracking(nums, used);
//         return res;
//     }

// 复盘
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>& nums, vector<bool>& used) {
        if(path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(i >  0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
            if(used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        path.clear();
        res.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, used);
        return res;
    }
};
// @lc code=end

